1. Technical Field
The present invention relates generally to circuit design, and more particularly, to a method, system and program product for scaling and area minimization of a circuit design.
2. Related Art
Circuit compaction is an integral part of integrated circuit (IC) chip design methodology for design optimization or migration. In conventional circuit compaction, a circuit design is reduced to its minimum legal size by building a constraint graph that represents the shape edges as nodes, and ground rules and topological relationships as arcs. Each node value represents the edge's current position, and each arc value represents the minimum separation between the edges connected by the arc. In order to illustrate, FIG. 1 shows an illustrative circuit design 8 constraint graph. In a typical circuit compactor, reduction of circuit design 8 is completed by assigning a graph node 10a–d to represent a location of every shape edge 12 that is perpendicular to the direction of compaction (CD), and one graph node 10e–f each to a “source” 14 and a “sink” 16, which are the boundaries of the design. In the example shown in FIG. 1, two rectangles 18 are positioned side-by-side. Accordingly, if compaction occurs in an “X” direction, a graph node 10a–f would represent every vertical edge 12 of each rectangle 18. Each graph node 10a–f has a value (its X position).
In FIG. 1, the locations to be assigned are X1, X2, X3, X4 and sink 16. Source 14 is fixed at the origin. In addition, each graph node 10a–f has an arc 20a–f that connects it to its neighbors, which represent constraints (ground rule values) on the locations X1–X4 and sink 16. For example, arc 20a and 20e may be half the minimum spacing for wires on metal layer one (M1) and may be, for example, 0.1 microns (these arcs thus represent a boundary condition); arc 20c may be the minimum M1 spacing, e.g., 0.2 microns; and arcs 20b and 20d may be the minimum width for an M1 wire, e.g., 0.2 microns. Arc 20f will be ignored for now.
In order to compact the design to a minimum size, a graph longest path algorithm is used to find the minimum distance from the boundary to each node, subject to the restrictions represented by the arcs. That is, classical compaction will assign the locations X1, X2, X3, X4 and sink 16 using the “longest path” algorithm. The longest path algorithm will assign, for example:
X1Source + 20a  0 + 0.10.1X2X1 + 20b0.1 + 0.20.3X3X2 + 20c0.3 + 0.20.5X4X3 + 20d0.5 + 0.20.7SinkX4 + 20e0.7 + 0.10.8
This configuration compacts rectangles 18 to their minimum legal size in the direction of compaction (CD).
One problem with conventional longest-path based compaction is that it is incapable of meeting all of the constraints which users place on the design. A completed circuit design is subject to constraints in the form of ground rules, which are well understood by conventional compaction. However, there are a number of other constraints that the designer has in mind while laying out the circuit. These constraints may relate to issues such as performance or yield objectives. Many of these constraints may not be able to be described geometrically, making them difficult to describe to a conventional compaction tool. For constraints that can be described, entering all of the user constraints into a compaction tool can be a task that is nearly as difficult as re-implementing the circuit from scratch.
Conventional longest path compaction algorithms cannot compact a design that contains a “positive cycle.” A positive cycle typically results if there are illegal shape configurations (ground rule incorrect starting point), or if there are constraints that restrict the area of the layout to less than the required size. If there is a positive cycle, then there is no longest path. Removing the positive cycle in a typical compactor does not correct the illegality that brought about the cycle, e.g., a broken ground rule or unachievable constraint. Relative to FIG. 1, a positive cycle can be illustrated by assuming a boundary constraint that fixes arc 20f at 0.6. In this case, every time a conventional compactor traverses the path 20a, 20b, 20c, 20d, 20e, 20f, the total cost increases by 0.2 (i.e., 0.1+0.2+0.2+0.2+0.1−0.6). In a shortest path algorithm, the equivalent problem is referred to as a “negative cycle.” In any case, the positive cycle represents a conflict in the constraints (arcs 20a–20f), not all of which can be met.
Another problem with classical compaction approaches is created by how the techniques create the maximum changes possible to the design. In particular, conventional compaction algorithms conduct “plowing” or squeezing of every shape as far as possible in the compaction direction, which can destroy symmetry or alignment that was present in the original design. For example, FIGS. 2A–2B illustrate two rows of elements in which the top row contains six (6) elements 30a–30f, and the bottom row contains only three (3) elements 32a–32c. In addition, every other top row element 30a, 30c, 30e is connected to one of the bottom row elements 30a, 30b, 30c, respectively. FIG. 2A illustrates an un-compacted layout, FIG. 2B illustrates a compacted layout using conventional compaction techniques including a “jog insertion” implementation such that wires can be bent as required. As illustrated in FIG. 2B, the layout is compacted in a legal manner, but the relative positions of elements 30a–30f and 32a–32c do not encompass the designer's original intent. This plowing of the layout prevents many designers from using a compactor because of the unpredictable and inelegant outcomes to the layout, which in turn prevents widespread use of compaction technology.
Minimum perturbation analysis (hereinafter referred to as “minpert”) is used to implement ground rule adjustments in circuit designs in a way that makes the minimum number of changes necessary. In particular, when a design has a minpert analysis applied, any of the arcs 20a–20f (FIG. 1) that are legal, are frozen. Any arcs 20a–20f that are not legal are fed to a linear system solver, which attempts to fix every arc that does not have a currently legal value, and minimize the overall differences in positions, i.e., X2−X1>=0.2. If X2−X1 is currently 0.1, then the system will try to change X2−X1, while minimizing X2(new)−X2 (old), and minimizing X1(new)−X1(old). U.S. Pat. No. 6,189,132 to Heng et al., which is hereby incorporated by reference, discloses a design rule correction system and method that implements minpert analysis. Unfortunately, minpert analysis does not address area minimization.
Rudimentary scaling has been used to perform compaction, but has led to unacceptable results for widespread use.
In view of the foregoing, there is a need in the art for an improved compaction method, system and program product for compacting a circuit design.